#ifndef __BINARYTREE_H_
#define __BINARYTREE_H_

#include <iostream>
#include <MyInclude/LinkQueue.h>

class BinaryTree
{
public:
    using ElementType = int;

    BinaryTree();
    ~BinaryTree();

    void Insert(const ElementType& element);
    void Remove(const ElementType& element);
    ElementType* Find(const ElementType& element);
    void show();
private:

    struct TreeNode
    {
        TreeNode(const ElementType &element):data(element)
        {
            left = right = parent = nullptr;
        }
        ElementType data;//数据域
        TreeNode *left;
        TreeNode *right;
        TreeNode *parent;
    };
    TreeNode* InsertNode(TreeNode *node,const ElementType& element);
    void PrevTravel(TreeNode *node);
    void MidTravel(TreeNode *node);
    void PostTravel(TreeNode *node);
    void Free(TreeNode *node);
    TreeNode* RemoveNode(TreeNode *node,const ElementType& element);
    TreeNode* GetMinNode(TreeNode *node);
    ElementType* FindNode(TreeNode *node,const ElementType& element);
    TreeNode* RotateRight(TreeNode *root);
    TreeNode* RotateLeft(TreeNode *root);
    TreeNode* RotateLeftRight(TreeNode *root);
    TreeNode* RotateRightLeft(TreeNode *root);
    int GetNodeHight(TreeNode *node);
    int LRDevition(TreeNode* node);
    TreeNode *root;
};




#endif